;;;; 2007-02-08 21:20:38
;;;; This is your lisp file. May it serve you well.

;(in-package :cse517a-hw1)

(defun sum (lst)
  (let ((total 0))
    (progn
      (dolist (val lst)
          (if (numberp val)
            (setf total (+ val total))))
      total)))

(defun mean (lst)
  (/ (sum lst) (length lst)))

(defun nth-mean (lst val)
  (mean (nth val (invert-list lst))))

(defun stddev (lst)
  (let ((m (mean lst)) (dev 0))
    (progn
      (dolist (val lst)
        (if (numberp val)
          (setf dev (+ dev (abs (- val m))))))
      (/ dev (length lst)))))

(defun variance (lst)
  (let ((m (mean lst)) (dev 0))
    (progn
      (dolist (val lst)
        (if (numberp val)
          (setf dev (+ dev (expt (- val m) 2)))))
      (/ dev (length lst)))))

(defun invert-list (lst)
  (let ((r nil))
    (progn
      (dotimes (i (length (car lst)))
        (setf r (cons (list ) r)))
      (dolist (sub lst)
        (dotimes (i (length sub))
          (setf (nth i r) (cons (nth i sub) (nth i r)))))
      r)))

                  


(defun stddev-list (lst)
  (let ((devs nil))
    (progn
      (dolist (cur lst)
        (setf devs (cons (stddev cur) devs)))
      (reverse devs))))

(defun rands (count range)
  (let ((r (list )))
    (progn
      (dotimes (i count)
        (setf r (cons (random range) r)))
      r)))

(defun randbin (count)
  (if (> count 1)
    (cons (random 10) (randbin (- count 1)))
    (cons (random 10) nil)))

(defun read-lists (file)
  (let ((lst nil))
    (progn
      (with-open-file (str file :direction :input)
        (do ((line (read str nil 'eof)
                   (read str nil 'eof)))
            ((eql line 'eof))
          (setf lst (cons line lst))))
      lst)))

(defun closeness (val entry using sdevs)
  (if (not (null val))
    (let ((sum 0))
      (dolist (element using)
        (if (and (not (= (nth element sdevs) 0)) (numberp (nth element val)) (numberp (nth element entry)))
          (setf sum (+ sum (/ (abs (- (nth element val) (nth element entry))) (nth element sdevs))))))
      sum)))

(defun slow-nearest-neighbor (data entry using k)
  (let ((test (remove entry data)) (nearest nil) (best nil) (sdevs (stddev-list (invert-list data))) (i 0))
    (loop
      (when (= i k)
        (return nearest))
      (dolist (val test)
        (if (null best)
            (progn
              (setf nearest (cons val nearest))
              (setf best (closeness val entry using sdevs)))
            (if (< (closeness val entry using sdevs) best)
                (progn
                  (setf nearest (cons val (cdr nearest)))
                  (setf best (closeness val entry using sdevs))))))
      (setf best nil)
      (setf i (+ 1 i))
      (setf test (remove (car nearest) test)))))

(defun lessp (a b)
  (> (car a) (car b)))

(defun nearest-neighbor (data entry using k)
  (let (
        (test (remove entry data)) 
        (nearest (create-heap #'lessp))
        (cur-closeness 0) 
        (sdevs (stddev-list (invert-list data))) 
        (result (list )))
    (progn
      (dolist (cur test)
        (setf cur-closeness (closeness cur entry using sdevs))
        (if (< (heap-count nearest) k) 
            (heap-insert nearest (list cur-closeness cur))
            (if (< cur-closeness (car (heap-peek nearest)))
                (progn
                  (heap-remove nearest)
                  (heap-insert nearest (list cur-closeness cur))))))
      (loop
        (when (= 0 (heap-count nearest))
          (return result))
        (setf result (cons (car (cdr (heap-remove nearest))) result))))))

(defun kernel (val entry using sdevs h)
  (exp (/ (- 0 (expt (closeness val entry using sdevs) 2)) (expt h 2))))

(defun lwa (data entry using h)
  (let ((test (remove entry data)) (k-sum 0.) (k-val-sum 0.) (sdevs (stddev-list (invert-list data))))
    (progn
      (dolist (cur test)
        (setf k-sum (+ k-sum (kernel cur entry using sdevs h)))
        (setf k-val-sum (+ k-val-sum (* (nth 0 cur) (kernel cur entry using sdevs h)))))
      (if (= 0 k-sum)
           0
           (/ k-val-sum k-sum)))))
      
(defun nn-expected (data entry using k)
  (let ((nearest (nearest-neighbor data entry using k)))
    (nth-mean nearest 0)))
    
(defun nn-dif (data entry using k)
  (abs (- (nn-expected data entry using k) (nth 0 entry))))

(defun lwa-dif (data entry using h)
  (abs (- (lwa data entry using h) (nth 0 entry))))

(defun nn-stddev (data test using k)
  (let ((difs (list )))
    (progn
      (dolist (entry test)
        (setf difs (cons (nn-dif data entry using k) difs)))
      (stddev difs))))

(defun nn-variance (data test using k)
  (let ((difs (list )))
    (progn
      (dolist (entry test)
        (setf difs (cons (nn-dif data entry using k) difs)))
      (variance difs))))

(defun lwa-variance (data test using k)
  (let ((difs (list )))
    (progn
      (dolist (entry test)
        (setf difs (cons (lwa-dif data entry using k) difs)))
      (variance difs))))

(defun random-elt (choices)
  (elt choices (random (length choices))))

(defun nfold (lst n)
  (let ((dlst lst) (folds (list )))
    (loop
      (when (= (length dlst) 0)
        (return folds))
      (setf folds (cons (list ) folds))
      (dotimes (i n)
        (when (= (length dlst) 0)
          (return folds))
        (setf (car folds) (cons (random-elt dlst) (car folds)))
        (setf dlst (remove (car (car folds)) dlst))))))
      
(defun nfold-with-set (lst n)
  (let ((folds (nfold lst n)) (dlst nil))
    (progn
      (dotimes (i (length folds))
        (setf dlst lst)
        (dolist (val (nth i folds))
          (setf dlst (remove val dlst)))
        (setf (nth i folds) (cons (nth i folds) dlst)))
      folds)))
          
(defun nfold-stddev (lst n using k)
  (let ((flst (nfold-with-set lst n)) (sdevs (list )))
    (progn
      (dolist (fold flst) 
        (setf sdevs (cons (nn-stddev (cdr fold) (car fold) using k) sdevs)))
      sdevs)))

(defun nfold-variance (lst n using k)
  (let ((flst (nfold-with-set lst n)) (vars (list )))
    (progn
      (dolist (fold flst) 
        (setf vars (cons (nn-variance (cdr fold) (car fold) using k) vars)))
      vars)))

(defun nfold-lwa-variance (lst n using k)
  (let ((flst (nfold-with-set lst n)) (vars (list )))
    (progn
      (dolist (fold flst) 
        (setf vars (cons (lwa-variance (cdr fold) (car fold) using k) vars)))
      vars)))

;(setf data (read-lists "F:/programming/cse517a-hw1/auto-mpg.data"))
;(setf data (read-lists "Desktop/auto-mpg.data"))
;(dotimes (i 4) (format t "~a: ~{~a~^, ~}~%" (+ 1 i) (nfold-variance data 20 (list 4) (+ 1 i))))      
;(dotimes (i 4) (format t "~a: ~{~a~^, ~}~%" (+ 1 i) (nfold-variance data 20 (list 1 2 3 4 5 6) (+ 1 i))))   
;(dotimes (i 4) (format t "~a: ~{~a~^, ~}~%" (+ 1 i) (nfold-lwa-variance data 20 (list 1 2 3 4 5 6) (+ 1 i))))  
;(dotimes (i 4) (format t "~a: ~{~a~^, ~}~%" (/ (+ 4 i) 10) (nfold-lwa-variance data 20 (list 1 2 3 4 5 6) (/ (+ 4 i) 10)))) 
;(nfold-lwa-variance data 20 (list 1 2 3 4 5 6) .4)
    
    